#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
long long a,b,mn[N],zs[N],pd[N],top,t,ans;
int main()
{
	freopen("never.in","r",stdin);
	freopen("never.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	for(int i=2;i<=N-5;++i)
	{
		if(!pd[i]) ++top,zs[top]=i;
		for(int j=1;j<=top&&zs[j]*i<=N-5;++j)
		{
			pd[zs[j]*i]=1;
			mn[i*zs[j]]=zs[j];
			if(i%zs[j]==0)
				break;
		}
	}
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		if(__gcd(a,b)==a)
		{
			cout<<b<<'\n';
			continue;
		}
		if(__gcd(a,b)==b)
		{
			cout<<a<<'\n';
			continue;
		}
		if(__gcd(a,b)!=1)
		{
			cout<<a+b<<'\n';
			continue;
		}
		ans=a+b;
		if(mn[a]==0) ans-=a;
		else a=mn[a];
		if(mn[b]==0) ans-=b;
		else b=mn[b];
		cout<<ans+min(2*(a+b),a*b)<<'\n';
	}
	return 0;
}
